package com.sword.algorithm.sudoku;

import javafx.scene.chart.PieChart;

import java.util.Date;

/**
 * 回溯法,解决
 * com.sword.algorithm.sudoku.sudoku
 * Created by SwordLiu on 2018-02-03.
 */
public class Sudoku {

    public static void main(String[] args) {
        int[][] arr = {
                {5, 3, 0, 0, 7, 0, 0, 0, 0},
                {6, 0, 0, 1, 9, 5, 0, 0, 0},
                {0, 9, 8, 0, 0, 0, 0, 6, 0},
                {8, 0, 0, 0, 6, 0, 0, 0, 3},
                {4, 0, 0, 8, 0, 3, 0, 0, 1},
                {7, 0, 0, 0, 2, 0, 0, 0, 6},
                {0, 6, 0, 0, 0, 0, 2, 8, 0},
                {0, 0, 0, 4, 1, 9, 0, 0, 5},
                {0, 0, 0, 0, 8, 0, 0, 7, 9}
        };
        char[][] cha = {
                {'5', '3', '0', '0', '7', '0', '0', '0', '0'},
                {'6', '0', '0', '1', '9', '5', '0', '0', '0'},
                {'0', '9', '8', '0', '0', '0', '0', '6', '0'},
                {'8', '0', '0', '0', '6', '0', '0', '0', '3'},
                {'4', '0', '0', '8', '0', '3', '0', '0', '1'},
                {'7', '0', '0', '0', '2', '0', '0', '0', '6'},
                {'0', '6', '0', '0', '0', '0', '2', '8', '0'},
                {'0', '0', '0', '4', '1', '9', '0', '0', '5'},
                {'0', '0', '0', '0', '8', '0', '0', '7', '9'}
        };
//        int[][] solution = solution(cha);
//        计算时间
        Date begin = new Date();
        boolean solution = solve(cha);
        Date end = new Date();
        System.out.println("用时：" + (end.getTime()-begin.getTime()));

//        输出结果
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (cha[i][j] == '0') {
                    System.out.print("_   ") ;
                }else {
                    System.out.print(cha[i][j] + "   ");
                }
                if ((j + 1) % 3 == 0) System.out.print("   ");
            }
            System.out.println();
            if ((i + 1) % 3 == 0) System.out.println();
        }
        System.out.println(solution);
    }

    private static boolean solve(char[][] board){
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == '0'){
                    for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
                        if(isValid(board, i, j, c)){
                            board[i][j] = c; //Put c for this cell

                            if(solve(board))
                                return true; //If it's the solution return true
                            else
                                board[i][j] = '0'; //Otherwise go back
                        }
                    }

                    return false;
                }
            }
        }
        return true;
    }

    private static boolean isValid(char[][] board, int row, int col, char c){
        int blockr = row / 3 * 3;
        int blockc = col / 3 * 3;
        for(int i = 0; i < 9; i++) {
            if(board[i][col] != '0' && board[i][col] == c) return false; //check row
            if(board[row][i] != '0' && board[row][i] == c) return false; //check column
            if(board[blockr + i / 3][ blockc + i % 3] != '0' &&
                    board[blockr + i / 3][blockc + i % 3] == c) return false; //check 3*3 block
        }
        return true;
    }

}
